#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include <iostream>
#include <algorithm>

using namespace std;

class UnderflowException { };
class IllegalArgumentException { };
class ArrayIndexOutOfBoundsException { };
class IteratorOutOfBoundsException { };
class IteratorMismatchException { };
class IteratorUninitializedException { };

/**
 * @brief Binary Tree class.
 *
 * This class represents a binary tree data structure.
 * It provides various operations like insertion, deletion,
 * finding minimum and maximum elements, checking if an element
 * is present in the tree, etc.
 *
 * @tparam Comparable The type of elements stored in the binary tree.
 */
template <typename Comparable>
class BinaryTree
{
public:
  virtual ~BinaryTree() {}

  /**
   * @brief Find the minimum element in the binary tree.
   *
   * @return The minimum element in the binary tree.
   */
  virtual const Comparable &findMin() = 0;

  /**
   * @brief Find the maximum element in the binary tree.
   *
   * @return The maximum element in the binary tree.
   */
  virtual const Comparable &findMax() = 0;

  /**
   * @brief Check if the binary tree contains a given element.
   *
   * @param x The element to be checked.
   * @return True if the element is found, false otherwise.
   */
  virtual bool contains(const Comparable &x) = 0;

  /**
   * @brief Check if the binary tree is empty.
   *
   * @return True if the binary tree is empty, false otherwise.
   */
  virtual bool isEmpty() const = 0;

  /**
   * @brief Make the binary tree empty.
   */
  virtual void makeEmpty() = 0;

  /**
   * @brief Insert an element into the binary tree.
   *
   * @param x The element to be inserted.
   */
  virtual void insert(const Comparable &x) = 0;

  /**
   * @brief Remove an element from the binary tree.
   *
   * @param x The element to be removed.
   */
  virtual void remove(const Comparable &x) = 0;

  /**
   * @brief Print the binary tree.
   *
   * This function prints the elements of the binary tree in a
   * specific order (e.g., in-order, pre-order, post-order).
   */
  virtual void printTree() const = 0;

protected:
  /**
   * @brief Binary Node struct.
   *
   * This struct represents a node in the binary tree.
   * It stores the element and pointers to the left and right child nodes.
   */
  struct BinaryNode
  {
    Comparable element; ///< The element stored in the node.
    BinaryNode *left;   ///< Pointer to the left child node.
    BinaryNode *right;  ///< Pointer to the right child node.

    /**
     * @brief Constructor for Binary Node.
     *
     * @param theElement The element to be stored in the node.
     * @param lt Pointer to the left child node.
     * @param rt Pointer to the right child node.
     */
    BinaryNode(const Comparable &theElement, BinaryNode *lt, BinaryNode *rt)
      : element{theElement}, left{lt}, right{rt} { }

    /**
     * @brief Constructor for Binary Node with move semantics.
     *
     * @param theElement The element to be stored in the node.
     * @param lt Pointer to the left child node.
     * @param rt Pointer to the right child node.
     */
    BinaryNode(Comparable &&theElement, BinaryNode *lt, BinaryNode *rt)
      : element{std::move(theElement)}, left{lt}, right{rt} { }
  };

  BinaryNode *root; ///< Pointer to the root node of the binary tree.
};

/**
 * @brief Binary search tree implementation.
 *
 * This class implements a binary search tree with the ability to insert, remove, and search for elements.
 * It is derived from the BinaryTree base class.
 *
 * @tparam Comparable The type of elements stored in the tree. It must support comparison operators (<, >, ==).
 */
template <typename Comparable>
class BinarySearchTree : public BinaryTree<Comparable>
{
public:
  /**
   * @brief Default constructor.
   *
   * Creates an empty binary search tree.
   */
  BinarySearchTree():root{nullptr}{}

  /**
   * @brief Copy constructor.
   *
   * Creates a new binary search tree that is a deep copy of the given tree.
   *
   * @param rhs The binary search tree to be copied.
   */
  BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
  {
    root = clone( rhs.root );
  }

  /**
   * @brief Move constructor.
   *
   * Creates a new binary search tree by moving the contents of the given tree.
   *
   * @param rhs The binary search tree to be moved.
   */
  BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root }
  {
    rhs.root = nullptr;
  }

  /**
   * @brief Destructor.
   *
   * Deletes all nodes in the binary search tree.
   */
  virtual ~BinarySearchTree() override
  {
    makeEmpty( );
  }

  /**
   * @brief Copy assignment operator.
   *
   * Makes a deep copy of the given binary search tree and assigns it to this tree.
   *
   * @param rhs The binary search tree to be copied.
   * @return A reference to this binary search tree.
   */
  BinarySearchTree & operator=( const BinarySearchTree & rhs )
  {
    BinarySearchTree copy = rhs;
    std::swap( *this, copy );
    return *this;
  }

  /**
   * @brief Move assignment operator.
   *
   * Moves the contents of the given binary search tree and assigns it to this tree.
   *
   * @param rhs The binary search tree to be moved.
   * @return A reference to this binary search tree.
   */
  BinarySearchTree & operator=( BinarySearchTree && rhs )
  {
    std::swap( root, rhs.root );       
    return *this;
  }

  /**
   * @brief Finds the minimum element in the tree.
   *
   * Throws an exception if the tree is empty.
   *
   * @return A reference to the minimum element in the tree.
   */
  const Comparable & findMin() override
  {
    if( isEmpty( ) )
      throw UnderflowException{ };
    return findMin(root)->element;
  }

  /**
   * @brief Finds the maximum element in the tree.
   *
   * Throws an exception if the tree is empty.
   *
   * @return A reference to the maximum element in the tree.
   */
  const Comparable & findMax() override
  {
    if( isEmpty( ) )
      throw UnderflowException{ };
    return findMax(root)->element;
  }

  /**
   * @brief Checks if the tree contains a given element.
   *
   * @param x The element to search for.
   * @return True if the element is found, false otherwise.
   */
  bool contains(const Comparable & x) override
  {
    return contains(x, root);
  }

  /**
   * @brief Checks if the tree is empty.
   *
   * @return True if the tree is empty, false otherwise.
   */
  bool isEmpty() const override
  {
    return root == nullptr;
  }

  /**
   * @brief Empties the tree.
   *
   * Deletes all nodes in the tree, making it empty.
   */
  void makeEmpty() override
  {
    makeEmpty(root);
  }

  /**
   * @brief Inserts an element into the tree.
   *
   * @param x The element to be inserted.
   */
  void insert(const Comparable & x) override
  {
    insert(x, root);
  }

  /**
   * @brief Inserts an rvalue element into the tree.
   *
   * @param x The rvalue element to be inserted.
   */
  void insert( Comparable && x ) 
  {
    insert( std::move( x ), root );
  }

  /**
   * @brief Removes an element from the tree.
   *
   * @param x The element to be removed.
   */
  void remove(const Comparable & x) override
  {
    remove(x, root);
  }

  /**
   * @brief Prints the elements of the tree in order.
   *
   * If the tree is empty, it prints "Empty tree".
   */
  void printTree() const override
  {
    if (isEmpty())
      cout << "Empty tree" << endl;
    else
      printTree(root);
  }
  
protected: 
  /**
   * @brief Node structure for the binary search tree.
   */
  struct BinaryNode
  {
    Comparable element; /**< The data contained in the node. */
    BinaryNode *left; /**< Pointer to the left child node. */
    BinaryNode *right; /**< Pointer to the right child node. */

    /**
     * @brief Constructor.
     *
     * @param theElement The data to be stored in the node.
     * @param lt Pointer to the left child node.
     * @param rt Pointer to the right child node.
     */
    BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
      : element{ theElement }, left{ lt }, right{ rt } { }

    /**
     * @brief Move constructor.
     *
     * @param theElement The data to be stored in the node (moved).
     * @param lt Pointer to the left child node.
     * @param rt Pointer to the right child node.
     */
    BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt )
      : element{ std::move( theElement ) }, left{ lt }, right{ rt } { }
  };
  
  BinaryNode* root; /**< Pointer to the root node. */

  /**
   * @brief Inserts an element into the tree.
   *
   * @param x The element to be inserted.
   * @param t The current node being checked.
   */
  void insert( const Comparable & x, BinaryNode* & t )
  {
    if( t == nullptr )
      t = new BinaryNode{ x, nullptr, nullptr };
    else if( x < t->element )
      insert( x, t->left );
    else if( t->element < x )
      insert( x, t->right );
    else
      ;  // Duplicate; do nothing
  }

  /**
   * @brief Inserts an rvalue element into the tree.
   *
   * @param x The rvalue element to be inserted.
   * @param t The current node being checked.
   */
  void insert( Comparable && x, BinaryNode * & t )
  {
    if( t == nullptr )
      t = new BinaryNode{ std::move( x ), nullptr, nullptr };
    else if( x < t->element )
      insert( std::move( x ), t->left );
    else if( t->element < x )
      insert( std::move( x ), t->right );
    else
      ;  // Duplicate; do nothing
  }

  /**
   * @brief Removes an element from the tree.
   *
   * @param x The element to be removed.
   * @param t The current node being checked.
   */
  void remove( const Comparable & x, BinaryNode * & t )
  {
    if( t == nullptr )
      return;   // Item not found; do nothing
    if( x < t->element )
      remove( x, t->left );
    else if( t->element < x )
      remove( x, t->right );
    else if( t->left != nullptr && t->right != nullptr ) // Two children
      {
	t->element = findMin( t->right )->element;
	remove( t->element, t->right );
      }
    else
      {
	BinaryNode *oldNode = t;
	t = ( t->left != nullptr ) ? t->left : t->right;
	delete oldNode;
      }
  }

  /**
   * @brief Finds the minimum element in the tree.
   *
   * @param t The current node being checked.
   * @return Pointer to the node containing the minimum element.
   */
  BinaryNode * findMin( BinaryNode *t ) const
  {
    if( t == nullptr )
      return nullptr;
    if( t->left == nullptr )
      return t;
    return findMin( t->left );
  }

  /**
   * @brief Finds the maximum element in the tree.
   *
   * @param t The current node being checked.
   * @return Pointer to the node containing the maximum element.
   */
  BinaryNode * findMax( BinaryNode *t ) const
  {
    if( t != nullptr )
      while( t->right != nullptr )
        t = t->right;
    return t;
  }

  /**
   * @brief Checks if the tree contains a given element.
   *
   * @param x The element to search for.
   * @param t The current node being checked.
   * @return True if the element is found, false otherwise.
   */
  bool contains( const Comparable & x, BinaryNode *t ) const
  {
    if( t == nullptr )
      return false;
    else if( x < t->element )
      return contains( x, t->left );
    else if( t->element < x )
      return contains( x, t->right );
    else
      return true;    // Match
  }

  /**
   * @brief Empties the tree.
   *
   * Deletes all nodes in the tree.
   *
   * @param t The current node being emptied.
   */
  void makeEmpty( BinaryNode * & t )
  {
    if( t != nullptr )
      {
	makeEmpty( t->left );
	makeEmpty( t->right );
	delete t;
      }
    t = nullptr;
  }

  /**
   * @brief Prints the elements of the tree in order.
   *
   * @param t The current node being printed.
   */
  void printTree( BinaryNode *t) const
  {
    if( t != nullptr )
      {
	printTree( t->left );
	cout << t->element << endl;
	printTree( t->right );
      }
  }

  /**
   * @brief Makes a deep copy of a binary search tree.
   *
   * @param t The current node being copied.
   * @return Pointer to the root of the copied tree.
   */
  BinaryNode * clone( BinaryNode *t ) const
  {
    if( t == nullptr )
      return nullptr;
    else
      return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) };
  }
};

//后面几类也是差不多的构造

template <typename Comparable>
class AvlTree : public BinaryTree<Comparable>
{
public:
  AvlTree():root{nullptr}{}
  AvlTree( const AvlTree & rhs ) : root{ nullptr }
  {
    root = clone( rhs.root );
  }
  AvlTree( AvlTree && rhs ) : root{ rhs.root }
  {
    rhs.root = nullptr;
  }
  virtual ~AvlTree() override
  {
    makeEmpty( );
  }
  
  AvlTree & operator=( const AvlTree & rhs )
  {
    AvlTree copy = rhs;
    std::swap( *this, copy );
    return *this;
  }

  AvlTree & operator=( AvlTree && rhs )
  {
    std::swap( root, rhs.root );       
    return *this;
  }
  
  const Comparable & findMin() override
  {
    if( isEmpty( ) )
      throw UnderflowException{ };
    return findMin(root)->element;
  }

  const Comparable & findMax() override
  {
    if( isEmpty( ) )
      throw UnderflowException{ };
    return findMax(root)->element;
  }
  
  bool contains(const Comparable & x) override
  {
    return contains(x, root);
  }
  
  bool isEmpty() const override
  {
    return root == nullptr;
  }
  
  void makeEmpty() override
  {
    makeEmpty(root);
  }
  
  void insert(const Comparable & x) override
  {
    insert(x, root);
  }

  void insert( Comparable && x ) 
  {
    insert( std::move( x ), root );
  }
  
  void remove(const Comparable & x) override
  {
    remove(x, root);
  }
  
  void printTree() const override
  {
    if (isEmpty())
      cout << "Empty tree" << endl;
    else
      printTree(root);
  }
  
   
protected:
  struct AvlNode 
  {
    Comparable element;
    AvlNode   *left;
    AvlNode   *right;
    int       height;

    AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 )
      : element{ ele }, left{ lt }, right{ rt }, height{ h } { }
        
    AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0 )
      : element{ std::move( ele ) }, left{ lt }, right{ rt }, height{ h } { }
   
  };
  
  AvlNode* root;
  
  void insert( const Comparable & x, AvlNode * & t )
  {
    if( t == nullptr )
      t = new AvlNode{ x, nullptr, nullptr };
    else if( x < t->element )
      insert( x, t->left );
    else if( t->element < x )
      insert( x, t->right );
    balance( t );
  }

  void insert( Comparable && x, AvlNode * & t )
  {
    if( t == nullptr )
      t = new AvlNode{ std::move( x ), nullptr, nullptr };
    else if( x < t->element )
      insert( std::move( x ), t->left );
    else if( t->element < x )
      insert( std::move( x ), t->right ); 
    balance(t);
  }
     
  void remove( const Comparable & x, AvlNode * & t )
  {
    if( t == nullptr )
      return;   // Item not found; do nothing
        
    if( x < t->element )
      remove( x, t->left );
    else if( t->element < x )
      remove( x, t->right );
    else if( t->left != nullptr && t->right != nullptr ) // Two children
      {
	t->element = findMin( t->right )->element;
	remove( t->element, t->right );
      }
    else
      {
	AvlNode *oldNode = t;
	t = ( t->left != nullptr ) ? t->left : t->right;
	delete oldNode;
      }
    balance( t );
  }
    
  static const int ALLOWED_IMBALANCE = 1;
  
  void balance( AvlNode * & t )
  {
    if( t == nullptr )
      return;
    
    if( height( t->left ) - height( t->right ) > ALLOWED_IMBALANCE )
      if( height( t->left->left ) >= height( t->left->right ) )
	rotateWithLeftChild( t );
      else
	doubleWithLeftChild( t );
    else
      if( height( t->right ) - height( t->left ) > ALLOWED_IMBALANCE )
	if( height( t->right->right ) >= height( t->right->left ) )
	  rotateWithRightChild( t );
	else
	  doubleWithRightChild( t );
                
    t->height = max( height( t->left ), height( t->right ) ) + 1;
  }
  
  AvlNode *findMin(AvlNode *t) const
  {
    if( t == nullptr )
      return nullptr;
    if( t->left == nullptr )
      return t;
    return findMin( t->left ); 
  }

  AvlNode *findMax(AvlNode *t) const
  {
    if( t != nullptr )
      while( t->right != nullptr )
	t = t->right;
    return t;
  }

  bool contains(const Comparable &x, AvlNode *t) const
  {
    if( t == nullptr )
      return false;
    else if( x < t->element )
      return contains( x, t->left );
    else if( t->element < x )
      return contains( x, t->right );
    else
      return true;   
  }

  void makeEmpty(AvlNode *&t)
  {
    if( t != nullptr )
      {
	makeEmpty( t->left );
	makeEmpty( t->right );
	delete t;
      }
    t = nullptr; 
  }

  void printTree(AvlNode *t) const
  {
    if( t != nullptr )
      {
	printTree( t->left );
	cout << t->element << endl;
	printTree( t->right );
      }
  }

  AvlNode *clone(AvlNode *t) const
  {
    if( t == nullptr )
      return nullptr;
    else
      return new AvlNode{ t->element, clone( t->left ), clone( t->right ), t->height };
  }
 
  int height( AvlNode *t ) const
  {
    return t == nullptr ? -1 : t->height;
  }

  int max( int lhs, int rhs ) const
  {
    return lhs > rhs ? lhs : rhs;
  }

  void rotateWithLeftChild( AvlNode * & k2 )
  {
    AvlNode *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
    k1->height = max( height( k1->left ), k2->height ) + 1;
    k2 = k1;
  }

  void rotateWithRightChild( AvlNode * & k1 )
  {
    AvlNode *k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = max( height( k1->left ), height( k1->right ) ) + 1;
    k2->height = max( height( k2->right ), k1->height ) + 1;
    k1 = k2;
  }

  void doubleWithLeftChild( AvlNode * & k3 )
  {
    rotateWithRightChild( k3->left );
    rotateWithLeftChild( k3 );
  }

  void doubleWithRightChild( AvlNode * & k1 )
  {
    rotateWithLeftChild( k1->right );
    rotateWithRightChild( k1 );
  }
};

template <typename Comparable>
class RedBlackTree: public BinaryTree<Comparable>
{
public:
  explicit RedBlackTree( const Comparable & negInf )
  {
    nullNode    = new RedBlackNode;
    nullNode->left = nullNode->right = nullNode;
        
    header      = new RedBlackNode{ negInf };
    header->left = header->right = nullNode;
  }
  RedBlackTree( const RedBlackTree & rhs )
  {
    nullNode    = new RedBlackNode;
    nullNode->left = nullNode->right = nullNode;
        
    header      = new RedBlackNode{ rhs.header->element };
    header->left = nullNode;
    header->right = clone( rhs.header->right );
  }
  RedBlackTree( RedBlackTree && rhs )
    : nullNode{ rhs.nullNode }, header{ rhs.header }
  {
    rhs.nullNode = nullptr;
    rhs.header = nullptr;
  }

  virtual ~RedBlackTree() override
  {
    makeEmpty( );
    delete nullNode;
    delete header;
  }
  
  RedBlackTree & operator=( const RedBlackTree & rhs )
  {
    RedBlackTree copy = rhs;
    std::swap( *this, copy );
    return *this;
  }
          
  RedBlackTree & operator=( RedBlackTree && rhs )
  {
    std::swap( header, rhs.header );
    std::swap( nullNode, rhs.nullNode );
        
    return *this;
  }
  
  const Comparable & findMin() override
  {
    if( isEmpty( ) )
      throw UnderflowException{ };

    RedBlackNode *itr = header->right;
    
    while( itr->left != nullNode )
      itr = itr->left;
    
    return itr->element;
  }

  const Comparable & findMax() override
  {
    if( isEmpty( ) )
      throw UnderflowException{ };

    RedBlackNode *itr = header->right;

    while( itr->right != nullNode )
      itr = itr->right;

    return itr->element;
  }

  bool contains(const Comparable & x) override
  {
    nullNode->element = x;
    RedBlackNode *curr = header->right;

    for( ; ; )
      {
	if( x < curr->element )
	  curr = curr->left;
	else if( curr->element < x )
	  curr = curr->right;
	else
	  return curr != nullNode;
      }
  }
  
  bool isEmpty() const override
  {
    return header->right == nullNode;
  }

  void printTree() const override
  {
    if( header->right == nullNode )
      cout << "Empty tree" << endl;
    else
      printTree( header->right );
  }
  
  void makeEmpty() override
  {
    if( header == nullptr )
      return;
        
    reclaimMemory( header->right );
    header->right = nullNode;
  }

  
  void insert( const Comparable & x ) override
  {
    current = parent = grand = header;
    nullNode->element = x;

    while( current->element != x )
      {
	great = grand; grand = parent; parent = current;
	current = x < current->element ?  current->left : current->right;
      
	// Check if two red children; fix if so
	if( current->left->color == RED && current->right->color == RED )
	  handleReorient( x );
      }
  
    // Insertion fails if already present
    if( current != nullNode )
      return;
    current = new RedBlackNode{ x, nullNode, nullNode };
  
    // Attach to parent
    if( x < parent->element )
      parent->left = current;
    else
      parent->right = current;
    handleReorient( x );
  }

  void remove(const Comparable & x) override
  {
    cout << "Sorry, remove unimplemented; " << x <<
      " still present" << endl;
  }
  
private:
  enum { RED, BLACK };
    
  struct RedBlackNode
  {
    Comparable    element;
    RedBlackNode *left;
    RedBlackNode *right;
    int           color;

    RedBlackNode( const Comparable & theElement = Comparable{ },
		  RedBlackNode *lt = nullptr, RedBlackNode *rt = nullptr,
		  int c = BLACK )
      : element{ theElement }, left{ lt }, right{ rt }, color{ c } { }
        
    RedBlackNode( Comparable && theElement, RedBlackNode *lt = nullptr,
		  RedBlackNode *rt = nullptr, int c = BLACK )
      : element{ std::move( theElement ) }, left{ lt }, right{ rt }, color{ c } { }
  };
  
  RedBlackNode *header= nullptr;
  RedBlackNode *nullNode= nullptr;
  RedBlackNode *current= nullptr;
  RedBlackNode *parent= nullptr;
  RedBlackNode *grand= nullptr;
  RedBlackNode *great= nullptr;

  void reclaimMemory( RedBlackNode *t )
  {
    if( t != t->left )
      {
	reclaimMemory( t->left );
	reclaimMemory( t->right );
	delete t;
      }
  }

  void printTree( RedBlackNode *t ) const
  {
    if( t != t->left )
      {
	printTree( t->left );
	cout << t->element << endl;
	printTree( t->right );
      }
  }

  RedBlackNode * clone( RedBlackNode * t ) const
  {
    if( t == t->left )  // Cannot test against nullNode!!!
      return nullNode;
    else
      return new RedBlackNode{ t->element, clone( t->left ),
	  clone( t->right ), t->color };
  }

  void handleReorient( const Comparable & item )
  {
    // Do the color flip
    current->color = RED;
    current->left->color = BLACK;
    current->right->color = BLACK;

    if( parent->color == RED )   // Have to rotate
      {
	grand->color = RED;
	if( item < grand->element != item < parent->element )
	  parent = rotate( item, grand );  // Start dbl rotate
	current = rotate( item, great );
	current->color = BLACK;
      }
    header->right->color = BLACK; // Make root black
  }

  RedBlackNode * rotate( const Comparable & item, RedBlackNode *theParent )
  {
    if( item < theParent->element )
      {
	item < theParent->left->element ?
	  rotateWithLeftChild( theParent->left )  :  // LL
	  rotateWithRightChild( theParent->left ) ;  // LR
	return theParent->left;
      }
    else
      {
	item < theParent->right->element ?
	  rotateWithLeftChild( theParent->right ) :  // RL
	  rotateWithRightChild( theParent->right );  // RR
	return theParent->right;
      }
  }

  void rotateWithLeftChild( RedBlackNode * & k2 )
  {
    RedBlackNode *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2 = k1;
  }

  void rotateWithRightChild( RedBlackNode * & k1 )
  {
    RedBlackNode *k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1 = k2;
  }
};

template <typename Comparable>
class SplayTree: public BinaryTree<Comparable>
{
public:
  SplayTree()
  {
    nullNode = new BinaryNode;
    nullNode->left = nullNode->right = nullNode;
    root = nullNode;
  }
  SplayTree( const SplayTree & rhs )
  {
    nullNode = new BinaryNode;
    nullNode->left = nullNode->right = nullNode;
    root = clone( rhs.root );
  }
  SplayTree( SplayTree && rhs ) : root{ rhs.root }, nullNode{ rhs.nullNode }
  {
    rhs.root = nullptr;
    rhs.nullNode = nullptr;
  }
  virtual ~SplayTree() override
  {
    makeEmpty( );
    delete nullNode;
  }

  SplayTree & operator=( const SplayTree & rhs )
  {
    SplayTree copy = rhs;
    std::swap( *this, copy );
    return *this;
  }
 
  SplayTree & operator=( SplayTree && rhs )
  {
    std::swap( root, rhs.root );
    std::swap( nullNode, rhs.nullNode );
    
    return *this;
  }
  
  const Comparable & findMin() override
  {
    if( isEmpty( ) )
      throw UnderflowException{ };

    BinaryNode *ptr = root;

    while( ptr->left != nullNode )
      ptr = ptr->left;

    splay( ptr->element, root );
    return ptr->element;
  }
  
  const Comparable & findMax() override
  {
    if( isEmpty( ) )
      throw UnderflowException{ };

    BinaryNode *ptr = root;
	
    while( ptr->right != nullNode )
      ptr = ptr->right;

    splay( ptr->element, root );
    return ptr->element;
  }

  bool contains(const Comparable & x)  override
  {
    if( isEmpty( ) )
      return false;
    splay( x, root );
    return root->element == x;
  }
  
  bool isEmpty() const override
  {
    return root == nullNode;
  }

  void printTree() const override
  {
    if( isEmpty( ) )
      cout << "Empty tree" << endl;
    else
      printTree( root );
  }
  
  void makeEmpty() override
  {
    while( !isEmpty( ) )
      {
	findMax( );       
	remove( root->element );
      }
  }
  
  void insert(const Comparable & x) override
  {
    static BinaryNode *newNode = nullptr;
    
    if( newNode == nullptr )
      newNode = new BinaryNode;
    newNode->element = x;
    
    if( root == nullNode )
      {
	newNode->left = newNode->right = nullNode;
	root = newNode;
      }
    else
      {
	splay( x, root );
	if( x < root->element )
	  {
	    newNode->left = root->left;
	    newNode->right = root;
	    root->left = nullNode;
	    root = newNode;
	  }
	else
	  if( root->element < x )
            {
	      newNode->right = root->right;
	      newNode->left = root;
	      root->right = nullNode;
	      root = newNode;
            }
	  else
	    return;
      }
    newNode = nullptr;  
  }

  void remove(const Comparable & x) override
  {
    if( !contains( x ) )
      return;   // Item not found; do nothing

    BinaryNode *newTree;

    if( root->left == nullNode )
      newTree = root->right;
    else
      {
	newTree = root->left;
	splay( x, newTree );
	newTree->right = root->right;
      }
    delete root;
    root = newTree;
  }

private:
  struct BinaryNode
  {
    Comparable  element;
    BinaryNode *left;
    BinaryNode *right;

    BinaryNode( ) : left{ nullptr }, right{ nullptr } { }
        
    BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
      : element{ theElement }, left{ lt }, right{ rt } { }       
  
  };
  BinaryNode* root;
  BinaryNode* nullNode;
  
  void reclaimMemory( BinaryNode * t )
  {
    if( t != t->left )
      {
	reclaimMemory( t->left );
	reclaimMemory( t->right );
	delete t;
      }
  }
    
  void printTree( BinaryNode *t ) const
  {
    if( t != t->left )
      {
	printTree( t->left );
	cout << t->element << endl;
	printTree( t->right );
      }
  }

  BinaryNode * clone( BinaryNode * t ) const
  {
    if( t == t->left )  // Cannot test against nullNode!!!
      return nullNode;
    else
      return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) };
  }

  void rotateWithLeftChild( BinaryNode * & k2 )
  {
    BinaryNode *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2 = k1;
  }

  void rotateWithRightChild( BinaryNode * & k1 )
  {
    BinaryNode *k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1 = k2;
  }

  void splay( const Comparable & x, BinaryNode * & t )
  {
    BinaryNode *leftTreeMax, *rightTreeMin;
    static BinaryNode header;

    header.left = header.right = nullNode;
    leftTreeMax = rightTreeMin = &header;

    nullNode->element = x;   // Guarantee a match

    for( ; ; )
      if( x < t->element )
	{
	  if( x < t->left->element )
	    rotateWithLeftChild( t );
	  if( t->left == nullNode )
	    break;
	  // Link Right
	  rightTreeMin->left = t;
	  rightTreeMin = t;
	  t = t->left;
	}
      else if( t->element < x )
	{
	  if( t->right->element < x )
	    rotateWithRightChild( t );
	  if( t->right == nullNode )
	    break;
	  // Link Left
	  leftTreeMax->right = t;
	  leftTreeMax = t;
	  t = t->right;
	}
      else
	break;

    leftTreeMax->right = t->left;
    rightTreeMin->left = t->right;
    t->left = header.right;
    t->right = header.left;
  }
};

#endif  // BINARY_TREE_H
